package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 12/16/20 10:23 AM
 */
public class _99_恢复二叉搜索树 {


    private TreeNode preNode;

    private TreeNode oneNode;

    private TreeNode twoNode;

    public void recoverTree(TreeNode root) {

        if (root == null) {

            return;
        }

        reversal(root);

        if (oneNode != null && twoNode != null) {

            int tmp = oneNode.val;
            oneNode.val = twoNode.val;
            twoNode.val = tmp;
        }
    }

    private void reversal(TreeNode root) {

        if (root == null) {

            return;
        }

        reversal(root.left);

        if (preNode != null && preNode.val > root.val) {

            twoNode = root;

            if (oneNode != null) {

                return;
            }

            oneNode = preNode;
        }

        preNode = root;
        reversal(root.right);
    }
}
